/**
 * https://leetcode.cn/problems/number-of-islands/submissions/550462142/
 * 200. 岛屿数量
 * medium, 陈贝纯 2024.07.28
 * 并查集
 */

class Solution {
public:
    void dfs(vector<vector<char>>& grid,int i,int j){
        int l=grid.size();
        int m=grid[0].size();
        grid[i][j]='0';
        if(i-1>=0&&grid[i-1][j]=='1') dfs(grid,i-1,j);
        if(i+1<l&&grid[i+1][j]=='1')  dfs(grid,i+1,j);
        if(j-1>=0&&grid[i][j-1]=='1') dfs(grid,i,j-1);
        if(j+1<m&&grid[i][j+1]=='1')  dfs(grid,i,j+1);
    }
    int numIslands(vector<vector<char>>& grid) {
        int l=grid.size();
        if(!l)
        return 0;
        int m=grid[0].size();
        int sum=0;
        for(int i=0;i<l;++i){
            for(int j=0;j<m;++j){
                if(grid[i][j]=='1'){
                    sum++;
                    dfs(grid,i,j);
                }
            }
        }
        return sum;
    }
};